package uns.fit.gis.alg;

import uns.fit.gis.mapobj.Crossroads;

/**
 * Binary heap implementation of a priority queue.<p>
 *
 * @see <a href="http://java.sun.com/products/j2se/1.5/docs/api/java/lang/Comparable.html">Comparable</a>
 * @see DataStructures.StrictBinaryHeap
 * @param <E> the type of elements held in this heap
 * @author Peter Williams
 */

public class MinHeap {

	private Crossroads[] heap; // the heap
	private int size; // number of items in the heap

	private RoutingAlgorithm alg;

	/**
	 * Constructs an empty binary heap suitable for holding elements of type E.
	 */
	public MinHeap(RoutingAlgorithm alg) {
		heap = new Crossroads[1];
		size = 0;

		this.alg = alg;
	}

	/**
	 * Tests if the heap is empty.
	 */
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * Returns the current size of the queue
	 */
	public int size() {
		return size;
	}

	/**
	 * Adds an item to the heap.
	 */
	public void add(Crossroads item) {
		// grow the heap if necessary
		if (size == heap.length) {
			Crossroads[] newHeap = new Crossroads[2 * heap.length];
			System.arraycopy(heap, 0, newHeap, 0, heap.length);
			heap = newHeap;
		}
		// find where to insert while rearranging the heap if necessary
		int parent, child = size++; // the next available slot in the heap
		while (child > 0 && compare(heap[parent = (child - 1) / 2], item) < 0) {
			heap[child] = heap[parent];
			child = parent;
		}
		heap[child] = item;
	}

	/**
	 * Removes an item of highest priority from the heap.
	 */
	public Crossroads remove() {
		if (size == 0) {
			return null;
		}
		Crossroads result = heap[0]; // to be returned
		Crossroads item = heap[--size]; // to be reinserted 
		int child, parent = 0;
		while ((child = (2 * parent) + 1) < size) {
			// if there are two children, compare them
			//if (child + 1 < size && heap[child].compareTo(heap[child + 1]) < 0) {
			if (child + 1 < size && compare(heap[child], heap[child + 1]) < 0) {
				++child;
			}
			// compare item with the larger
			if (compare(item, heap[child]) < 0) {
				heap[parent] = heap[child];
				parent = child;
			} else {
				break;
			}
		}
		heap[parent] = item;
		return result;
	}

	private int compare(Crossroads cross0, Crossroads cross1) {
		if (alg.getDistanceArray()[cross0.getId()] == alg.getDistanceArray()[cross1.getId()])
			return 0;
		else if (alg.isGreater(alg.getDistanceArray()[cross0.getId()], alg.getDistanceArray()[cross1.getId()]))
			return 1;
		else
			return -1;
	}
}
